1. Field of the Invention
The present invention relates to a method of electronic signing and an apparatus using the same and in particular relates to a method and apparatus for electronic signing which can confirm legitimacy of the signature without performing actual verification of the signature.
2. Discussion of the Related Art
It is now realized that a person who wants to receive some kinds of services such as using a computer program or watching and listening to the broadcasting program should electronically execute signature so that persons capable of receiving services may be limited to those who have executed the signature. Hereinafter such signature is called digital signature.
Japanese Patent Application Laid-Open No. Hei. 4-334227 (1992) discloses a method of forcing a user of charged broadcasting program to execute the digital signature on fee imposition information so that future denial of use of the charged program may be prevented. According to the invention of the Laid-Open publication, an encrypted program and a decryption key for decrypting the encrypted program are transmitted to a broadcasting program receiving decoder from the broadcasting station. The decoder receives the request for providing a program from the receiver, and notifies the receiver of the amount of the fee imposed on watching and listening to the program. If the amount of the fee is acceptable to the receiver, he/she executes digital signature with respect to the amount of the fee and returns it to the decoder. Then the decoder examines the returned digital signature of the amount of the fee to verify whether the signature is generated by a legitimate receiver. After legitimacy of the signature is verified, the decoder decrypts the requested program by the key obtained in advance, and provides the program to the receiver.
To execute such digital signature, public key encryption is used. That is, a public key pair is provided to each receiver and he/she publishes the public key, whereas he/she holds a private key in secret.
The digital signature on the data is generated by signature computation algorithm which has been published based on the input of data and the private key of a user. The verification of the digital signature is executed by a verification algorithm which has been also published based on the input of the data, signature on the data and the user's public key. For example, in the method disclosed by the Japanese Patent Application Laid-Open No. Hei. 4-334227, a basic Rivest-Shamir-Adleman (RSA) signature is employed and the signature computation algorithm and the verification algorithm are provided as follows:
Signature computation algorithm
Input: data x, a user's private key d and a public modulus n
Output: signature y=x.sup.d mod n
Verification algorithm
Input: data x, signature y on the data x, a user's public key e and a public modulus n
Output: true or false value z ##EQU1## The legitimacy of the public key is verified by a certificate issued by a public certificate authority. The certificate and the certificate authority are prescribed in, for example, CCITT X. 509.
The certificate is issued by a certificate authority which the user belongs to, and is made by a pair of a body of the certificate containing information such as a distinguished name of the user, a user's public key, etc., and a digital signature made by using the private key of the certificate authority on the body of the certificate. The certificate is used for legitimately obtaining user's public key. That is, a verifier (other user or system) who receives presentation of the certificate verifies the signature of the certificate by utilizing the public key of the certificate authority. If the verification results in success, it can be confirmed that the user's public key prescribed in the certificate is formally approved by the certificate authority.
The legitimacy of public key of the certificate authority itself is also verified by the fact that it is obtained through a certificate issued by another certificate authority. That is, a verifier who is to verify the legitimacy of a user's public key obtains a public key of a certificate authority based on a certificate issued by the other certification issued by the certificate authority whose public key is already known to the verifier, and based on the public key of the certificate authority, the verifier further obtains a public key of another certificate authority. By repeating the above procedure for a number of times as necessary, the verifier finally obtains a public key of the certificate authority who have issued a certificate for the user's public key.
As described above, it is necessary to legitimately obtain the user's public key for verifying the digital signature executed by the user, and thereby it is necessary to verify certificates constituting a chain for the required number. The chain of certificates is called a certification path, which is different by each user.
If the verification of the signature is considered in the case of the method disclosed by the Japanese Patent Application Laid-Open No. Hei. 4-334227, to perform verification of user's signature on the amount of fee by the decoder, it is necessary to obtain the user's public key by traversing the certification path by repeating the above procedure, or to register the public key of the user in the decoder in advance.
Fee imposition on the use of services is not limited to the charged broadcasting program. For example, fee imposition on application programs used in computers is widely known. In addition, as the computer infrastructures such as networks are established, extended and developed, fee imposition on services related to computers shows a tendency to develop more and more.
The variation in styles in using computers has been wider than before. In particular, it is unnecessary for the user to stick to a single computer (terminal); therefore, he/she can use various kinds of applications on any computer available for him/her in any place, for example, in the office, at home, or in some place on a business trip.
In the case as described above where it cannot be predicted who will use a specific computer, it is not practical to register the user's public key when the computer or the fee-imposing device installed in the computer is manufactured. However, there occurs a problem of computing efficiency if the verification of the certification path is made in every use of applications. There also exists disadvantage in the manufacturing cost. The method of registering the public key in the computer or fee-imposing device is most practical, but there is then a weak point with respect to attacks such as "Impersonation" at the time of registration.
As described so far, in the case where function to prevent denial is desired to be improved by forcing the user to execute digital signature on usage information such as fee imposition information for the use of an application program implemented on a computer, verification of the digital signature must be performed on all such occasions. Thus there have been problems in the points of manufacturing cost, computation efficiency and security.